package org.xiaoxin.leetcode.array;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 128. 最长连续序列
 * <p>
 * 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
 * <p>
 * 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
 *
 * @author xiaoxin
 */
public class _128_longestConsecutive {

    /**
     * 方法一：排序法（时间复杂度 O(n log n)）
     * 思路：先排序，然后遍历数组找连续序列
     */
    public static int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        Arrays.sort(nums);
        int count = 1;
        int tmpCount = 0;
        int min = nums[0];

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == min + 1) {
                min++;
                count++;
            } else if (nums[i] == min) {
                continue;
            } else {
                if (tmpCount < count) {
                    tmpCount = count;
                }
                count = 1;
                min = nums[i];
            }
        }
        return Math.max(tmpCount, count);
    }

    /**
     * 方法二：哈希集合法（时间复杂度 O(n)）
     * 思路：
     * 1. 将所有数字放入HashSet，实现O(1)的查找
     * 2. 遍历数组中的每个数字
     * 3. 对于每个数字num，检查num-1是否存在：
     * - 如果num-1存在，说明num不是连续序列的起点，跳过
     * - 如果num-1不存在，说明num是连续序列的起点，开始计算长度
     * 4. 从起点开始，依次检查num+1, num+2, ...是否存在，计算连续长度
     * 5. 更新最大长度
     * <p>
     * 时间复杂度：O(n) - 每个数字最多被访问两次
     * 空间复杂度：O(n) - HashSet存储所有数字
     */
    public static int longestConsecutiveOptimal(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        // 将所有数字放入HashSet
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }

        int maxLength = 0;

        // 遍历所有数字
        for (int num : numSet) {
            // 如果num-1不存在，说明num是连续序列的起点
            if (!numSet.contains(num - 1)) {
                int currentNum = num;
                int currentLength = 1;

                // 从起点开始，计算连续序列的长度
                while (numSet.contains(currentNum + 1)) {
                    currentNum++;
                    currentLength++;
                }

                // 更新最大长度
                maxLength = Math.max(maxLength, currentLength);
            }
        }

        return maxLength;
    }

    public static void main(String[] args) {
        testBothMethods();
    }

    private static void testBothMethods() {
        System.out.println("=== 测试两种算法的结果对比 ===\n");

        // 示例 1
        int[] nums1 = {100, 4, 200, 1, 3, 2};
        testCase("示例 1", nums1, 4);

        // 示例 2
        int[] nums2 = {0, 3, 7, 2, 5, 8, 4, 6, 0, 1};
        testCase("示例 2", nums2, 9);

        // 示例 3
        int[] nums3 = {1, 2, 0, 1};
        testCase("示例 3", nums3, 3);

        // 示例 4
        int[] nums4 = {9, 1, 4, 7, 3, -1, 0, 5, 8, -1, 6};
        testCase("示例 4", nums4, 7);

        // 空数组测试
        int[] nums5 = {};
        testCase("空数组测试", nums5, 0);

        // 单个元素测试
        int[] nums6 = {1};
        testCase("单个元素测试", nums6, 1);

        // 重复元素测试
        int[] nums7 = {1, 1, 1, 1};
        testCase("重复元素测试", nums7, 1);

        // 负数测试
        int[] nums8 = {-3, -2, -1, 0, 1, 2};
        testCase("负数测试", nums8, 6);

        // 不连续数组测试
        int[] nums9 = {1, 3, 5, 7, 9};
        testCase("不连续数组测试", nums9, 1);
    }

    private static void testCase(String testName, int[] nums, int expected) {
        System.out.println(testName + ":");
        System.out.println("输入: " + Arrays.toString(nums));

        int result1 = longestConsecutive(nums.clone());
        int result2 = longestConsecutiveOptimal(nums.clone());

        System.out.println("排序法结果: " + result1);
        System.out.println("哈希集合法结果: " + result2);
        System.out.println("期望结果: " + expected);

        boolean correct = (result1 == expected && result2 == expected);
        System.out.println("测试结果: " + (correct ? "✅ 通过" : "❌ 失败"));

        if (result1 != result2) {
            System.out.println("⚠️  警告: 两种方法结果不一致!");
        }

        System.out.println();
    }
}
